home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / SRC1229A.ARJ / LZW.C < prev    next >
C/C++ Source or Header  |  1990-11-11  |  15KB  |  551 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. #include "global.h"
  10. #include "mbuf.h"
  11. #include "proc.h"
  12. #include "lzw.h"
  13. #include "usock.h"
  14.  
  15. static void fastencode __ARGS((struct usock *up,char data));
  16. static int16 zhash __ARGS((int32 code,char data));
  17. static void morebits __ARGS((struct lzw *lzw));
  18. static void cleartbl __ARGS((struct lzw *lzw));
  19. static void addtobuffer __ARGS((struct usock *up,int32 code));
  20. static void addchar __ARGS((char data,struct lzw *lzw));
  21. static void getstring __ARGS((int32 code,struct lzw *lzw));
  22. static char firstchar __ARGS((int32 code,struct lzw *lzw));
  23. static void decodetbl __ARGS((int32 code,struct lzw *lzw));
  24. static int32 nextcode __ARGS((struct usock *up));
  25.  
  26. /* Initialize a socket for compression. Bits specifies the maximum number
  27.  * of bits per codeword. The input and output code tables might grow to
  28.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  29.  * recommendation for the decoding, the actual number of bits may be
  30.  * larger, but not never more than 16.
  31.  */
  32. void
  33. lzwinit(s,bits,mode)
  34. int s;        /* socket to operate on */
  35. int bits;    /* maximum number of bits per codeword */
  36. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  37. {
  38.     struct usock *up;
  39.     if((up = itop(s)) == NULLUSOCK)
  40.         return;
  41.     up->zout = (struct lzw *) callocw(1,sizeof(struct lzw));
  42.     up->zin = (struct lzw *) callocw(1,sizeof(struct lzw));
  43.     up->zout->codebits = LZWBITS;
  44.     if(bits < LZWBITS)
  45.         up->zout->maxbits = LZWBITS;
  46.     if(bits > 16 || bits == 0)
  47.         up->zout->maxbits = 16;
  48.     if(bits >= LZWBITS && bits <= 16)
  49.         up->zout->maxbits = bits;
  50.     up->zout->nextbit = 0;
  51.     up->zout->prefix = -1;
  52.     up->zout->version = -1;
  53.     up->zout->code = -1;
  54.     up->zout->mode = mode;
  55.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  56.     up->zin->codebits = LZWBITS;
  57.     up->zin->maxbits = -1;
  58.     up->zin->nextbit = 0;
  59.     up->zin->prefix = -1;
  60.     up->zin->version = -1;
  61.     up->zin->code = -1;
  62.     up->zin->next = ZFLUSH + 1;
  63.     up->zin->mode = LZWCOMPACT;
  64.     up->zin->buf = NULLBUF;
  65. }
  66.  
  67. void
  68. lzwfree(up)
  69. struct usock *up;
  70. {
  71.     if(up->zout != NULLLZW) {
  72.         cleartbl(up->zout);
  73.         free((char *)up->zout);
  74.         up->zout = NULLLZW;
  75.     }
  76.     up->zout = NULLLZW;
  77.     if(up->zin != NULLLZW) {
  78.         cleartbl(up->zin);
  79.         free_q(&up->zin->buf);
  80.         free((char *)up->zin);
  81.         up->zin = NULLLZW;
  82.     }
  83. }
  84. /* LZW encoding routine.
  85.  * See if the string specified by code + data is in the string table. If so,
  86.  * set prefix equal to the code of that string. Otherwise insert code + data
  87.  * in the string and set prefix equal to data.
  88.  */
  89. void
  90. lzwencode(s,data)
  91. int s;
  92. char data;
  93. {
  94.     struct usock *up;
  95.     register struct lzw *lzw;
  96.     int32 code, pagelim;
  97.     register unsigned int i,j;
  98.  
  99.     if((up = itop(s)) == NULLUSOCK)
  100.         return;
  101.     lzw = up->zout;
  102.     code = up->zout->prefix;
  103.     /* the first byte sent will be the version number */
  104.     if(lzw->version == -1) {
  105.         lzw->version = ZVERSION;
  106.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  107.         /* then send our recommended maximum number of codebits */
  108.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  109.     }
  110.     lzw->cnt++;
  111.     if(code == -1) {
  112.         lzw->prefix = (int32) uchar(data);
  113.         return;
  114.     }
  115.     if(lzw->mode == LZWFAST) {
  116.         fastencode(up,data);
  117.         return;
  118.     }
  119.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  120.     if(code <= ZFLUSH)
  121.         i = j = 0;
  122.     else {
  123.         i = (code - ZFLUSH) / LZWBLK;
  124.         j = (code - ZFLUSH) % LZWBLK;
  125.     }
  126.     if(lzw->tu.tbl == (struct zentry **)0)
  127.         lzw->tu.tbl = (struct zentry **) callocw(1,
  128.             sizeof(struct zentry *) * pagelim);
  129.     for(;;) {
  130.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  131.             return;
  132.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  133.             return;
  134.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  135.             lzw->tu.tbl[i] = (struct zentry *)
  136.                 mallocw(LZWBLK * sizeof(struct zentry));
  137.             memset((char *)lzw->tu.tbl[i], 0xff,
  138.                 LZWBLK * sizeof(struct zentry));
  139.         }
  140.         while(j < LZWBLK) {
  141.             if(lzw->tu.tbl[i][j].data == data &&
  142.                 lzw->tu.tbl[i][j].code == (int16) code) {
  143.                 lzw->prefix = (int32)(i * LZWBLK + j +
  144.                               ZFLUSH + 1);
  145.                 return;
  146.             }
  147.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  148.                 lzw->tu.tbl[i][j].code = (int16) code;
  149.                 lzw->tu.tbl[i][j].data = data;
  150.                 addtobuffer(up,code);
  151.                 lzw->prefix = (int32) uchar(data);
  152.                 lzw->next++;
  153.                 if(lzw->next ==    (int32) 1 << lzw->codebits)
  154.                     /* the current table is now full */
  155.                     morebits(lzw);
  156.                 if(lzw->next + 1 == (int32)
  157.                         1 << lzw->maxbits) {
  158.                 /* The last codeword has been reached.
  159.                  * (Or last - 1.) Signal this and start all
  160.                  * over again.
  161.                  */
  162.                     addtobuffer(up,lzw->prefix);
  163.                        if(lzw->next + 1 == (int32)
  164.                             1 << lzw->codebits)
  165.                         morebits(lzw);
  166.                     addtobuffer(up,ZCC);
  167.                     cleartbl(lzw);
  168.                 }
  169.                 return;
  170.             }
  171.             ++j;
  172.         }
  173.         pwait(NULL);
  174.         ++i;
  175.         j = 0;
  176.     }
  177. }
  178.  
  179. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  180.  * bytes.
  181.  */
  182. static void
  183. fastencode(up,data)
  184. struct usock *up;
  185. char data;
  186. {
  187.     register struct zfast *z;
  188.     register struct mbuf *bp;
  189.     register struct lzw *lzw = up->zout;
  190.     int32 code = up->zout->prefix;
  191.     register int16 cnt, h;
  192.  
  193.     if(lzw->tu.bpp == NULLBUFP)
  194.         lzw->tu.bpp = (struct mbuf **) callocw(1,
  195.             sizeof(struct mbuf *) * ZHASH);
  196.     h = zhash(code,data);
  197.     if(lzw->tu.bpp[h] == NULLBUF)
  198.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  199.     bp = lzw->tu.bpp[h];
  200.     cnt = bp->cnt / sizeof(struct zfast);
  201.     z = (struct zfast *) bp->data;
  202.     while(cnt > 0) {
  203.         if(z->data == data && z->code == (int16) code) {
  204.             lzw->prefix = (int32) z->owncode;
  205.             return;
  206.         }
  207.         z++;
  208.         if(--cnt == 0) {
  209.             if(bp->next == NULLBUF)
  210.                 break;
  211.             bp = bp->next;
  212.             cnt = bp->cnt / sizeof(struct zfast);
  213.             z = (struct zfast *) bp->data;
  214.         }
  215.     }
  216.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  217.         z = (struct zfast *) &bp->data[bp->cnt];
  218.         bp->cnt += sizeof(struct zfast);
  219.     }
  220.     else {
  221.         bp->next = ambufw(LZWBLK);
  222.         z = (struct zfast *) bp->next->data;
  223.         bp->next->cnt = sizeof(struct zfast);
  224.     }
  225.     z->code = (int16) code;
  226.     z->data = data;
  227.     z->owncode = (int16) lzw->next++;
  228.     addtobuffer(up,code);
  229.     lzw->prefix = (int32) uchar(data);
  230.     if(lzw->next == (int32) 1 << lzw->codebits) {
  231.         /* Increase the number of bits per codeword */
  232.         morebits(lzw);
  233.     }
  234.     if(lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  235.         /* The last codeword has been reached. (Or last - 1.)
  236.          * Signal this and start all over again.
  237.          */
  238.         addtobuffer(up,lzw->prefix);
  239.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  240.             morebits(lzw);
  241.         addtobuffer(up,ZCC);
  242.         cleartbl(lzw);
  243.     }
  244.     pwait(NULL);
  245. }
  246.  
  247. static int16
  248. zhash(code,data)
  249. int32 code;
  250. char data;
  251. {
  252.     register int16 h;
  253.     h = lobyte(code);
  254.     h ^= hibyte(code);
  255.     h ^= data;
  256.     return h % ZHASH;
  257. }
  258.  
  259. /* increase the number of significant bits in the codewords, and increase
  260.  * the size of the string table accordingly.
  261.  */
  262. static void
  263. morebits(lzw)
  264. struct lzw *lzw;
  265. {
  266.     struct zentry **newt;
  267.     int32 pagelim, oldp;
  268.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  269.     lzw->codebits++;
  270.     if(lzw->mode == LZWFAST)
  271.         return;
  272.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  273.     newt = (struct zentry **) callocw(1,sizeof(struct zentry *)*pagelim);
  274.     memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * oldp);
  275.     free((char *)lzw->tu.tbl);
  276.     lzw->tu.tbl = newt;
  277. }
  278.  
  279. static void
  280. cleartbl(lzw)
  281. struct lzw *lzw;
  282. {
  283.     int32 pagelim,i;
  284.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  285.     lzw->codebits = LZWBITS;
  286.     lzw->prefix = -1;
  287.     lzw->next = ZFLUSH + 1;
  288.     if(lzw->tu.p == NULL)
  289.         return;
  290.     if(lzw->mode == LZWCOMPACT)
  291.         for(i=0; i < pagelim; ++i)
  292.             free((char *)lzw->tu.tbl[i]);
  293.     else
  294.         for(i=0; i < ZHASH; ++i)
  295.             free_p(lzw->tu.bpp[i]);
  296.     free((char *)lzw->tu.p);
  297.     lzw->tu.p = NULL;
  298. }
  299. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  300.  * code stream should be written first. The codeword ZFLUSH is used to
  301.  * pad the buffer to a byte boundary when the buffer will be flushed.
  302.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  303.  */
  304. static void
  305. addtobuffer(up,code)
  306. struct usock *up;
  307. int32 code;
  308. {
  309.     if(up->zout->code != -1) {
  310.         /* Insert remaining bits of ZFLUSH codeword */
  311.         up->obuf->data[up->obuf->cnt] =
  312.              up->zout->code >> up->zout->flushbit;
  313.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  314.             up->zout->nextbit = (up->zout->codebits -
  315.                         up->zout->flushbit) % 8;
  316.             if(up->zout->nextbit == 0)
  317.                 ++up->obuf->cnt;
  318.             up->zout->code = -1;
  319.         }
  320.         else {
  321.             /* not done yet */
  322.             ++up->obuf->cnt;
  323.             up->zout->flushbit += 8;
  324.             addtobuffer(up,code);
  325.             return;
  326.         }
  327.     }
  328.     /* normal codewords are treated here */
  329.     if(up->zout->nextbit == 0) {
  330.         /* we are at a byte boundary */
  331.         if(code == ZFLUSH) {
  332.             up->zout->flushbit = 0;
  333.             up->zout->code = ZFLUSH;
  334.             return;
  335.         }
  336.         up->obuf->data[up->obuf->cnt++] = (char) code;
  337.     }
  338.     else
  339.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  340.     if(code == ZFLUSH) {
  341.         /* interrupt here and save the rest of the ZFLUSH
  342.          * codeword for later.
  343.          */
  344.         up->zout->flushbit = 8 - up->zout->nextbit;
  345.         up->zout->code = ZFLUSH;
  346.         return;
  347.     }
  348.     up->obuf->data[up->obuf->cnt] = code >> 8 - up->zout->nextbit;
  349.     /* start on a third byte if necessary */
  350.     if(16 - up->zout->nextbit < up->zout->codebits)
  351.         up->obuf->data[++up->obuf->cnt] =
  352.                     code >> 16 - up->zout->nextbit;
  353.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  354.     if(up->zout->nextbit == 0)
  355.         ++up->obuf->cnt;
  356. }
  357.  
  358. void
  359. lzwflush(up)
  360. struct usock *up;
  361. {
  362.     /* interrupt the encoding process and send the prefix codeword */
  363.     if(up->zout->prefix != -1) {
  364.         addtobuffer(up,up->zout->prefix);
  365.            if(up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  366.             morebits(up->zout);
  367.         up->zout->prefix = -1;
  368.     }
  369.     /* signal this by sending the ZFLUSH codeword */
  370.     addtobuffer(up,ZFLUSH);
  371. }
  372.  
  373. int
  374. lzwdecode(up)
  375. struct usock *up;
  376. {
  377.     int32 code,data;
  378.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf))
  379.        == -1)
  380.         return -1;
  381.     if(up->zin->maxbits == -1) {
  382.         /* receive a recommended value for the maximum no of bits */
  383.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  384.             return -1;
  385.         if(up->zout->maxbits > up->zin->maxbits) {
  386.             if(up->zout->codebits > up->zin->maxbits) {
  387.                 /* We are already using more bits than our
  388.                  * peer want us to, so clear the encoding
  389.                  * table immediately.
  390.                  */
  391.                 addtobuffer(up,up->zout->prefix);
  392.                 if(up->zout->next + 1 == (int32)
  393.                    1 << up->zout->codebits)
  394.                     morebits(up->zout);
  395.                 addtobuffer(up,ZCC);
  396.                 cleartbl(up->zout);
  397.             }
  398.             up->zout->maxbits = up->zin->maxbits;
  399.         }
  400.     }
  401.     for(;;) {
  402.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  403.             return (int) data;
  404.         if((code = nextcode(up)) == -1)
  405.             return -1;
  406.         decodetbl(code,up->zin);
  407.         up->zin->cnt += len_p(up->zin->buf);
  408.     }
  409. }
  410.  
  411. static void
  412. addchar(data,lzw)
  413. char data;
  414. struct lzw *lzw;
  415. {
  416.     lzw->buf = pushdown(lzw->buf,1);
  417.     *lzw->buf->data = data;
  418. }
  419. static void
  420. getstring(code,lzw)
  421. int32 code;
  422. struct lzw *lzw;
  423. {
  424.     int i,j;
  425.     for(;;) {
  426.         if(code < ZFLUSH) {
  427.             addchar(uchar(code),lzw);
  428.             return;
  429.         }
  430.         i = (code - ZFLUSH - 1) / LZWBLK;
  431.         j = (code - ZFLUSH - 1) % LZWBLK;
  432.         addchar(lzw->tu.tbl[i][j].data,lzw);
  433.         code = (int32) lzw->tu.tbl[i][j].code;
  434.     }
  435. }
  436. static char
  437. firstchar(code,lzw)
  438. int32 code;
  439. struct lzw *lzw;
  440. {
  441.     int i,j;
  442.     for(;;) {
  443.         if(code < ZFLUSH)
  444.             return uchar(code);
  445.         i = (code - ZFLUSH - 1) / LZWBLK;
  446.         j = (code - ZFLUSH - 1) % LZWBLK;
  447.         code = (int32) lzw->tu.tbl[i][j].code;
  448.     }
  449. }
  450. static void
  451. decodetbl(code,lzw)
  452. int32 code;
  453. struct lzw *lzw;
  454. {
  455.     register unsigned int i,j;
  456.     int32 pagelim;
  457.  
  458.     if(code > lzw->next) {
  459.         printf("LZW protocol error, process %s\n",Curproc->name);
  460.         return;
  461.     }
  462.     if(lzw->buf == NULLBUF) {
  463.         lzw->buf = ambufw(512);
  464.         /* allow us to use pushdown() later */
  465.         lzw->buf->data += lzw->buf->size;
  466.     }
  467.     if(lzw->prefix == -1) {
  468.         getstring(code,lzw);
  469.         lzw->prefix = code;
  470.         return;
  471.     }
  472.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  473.     if(lzw->tu.tbl == (struct zentry **)0)
  474.         lzw->tu.tbl = (struct zentry **) callocw(1,
  475.                 sizeof(struct zentry *) * pagelim);
  476.     if(code < ZFLUSH)
  477.         goto intable;
  478.     i = (code - ZFLUSH - 1) / LZWBLK;
  479.     j = (code - ZFLUSH - 1) % LZWBLK;
  480.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  481.         lzw->tu.tbl[i] = (struct zentry *)
  482.                 mallocw(LZWBLK * sizeof(struct zentry));
  483.         memset((char *)lzw->tu.tbl[i], 0xff,
  484.                 LZWBLK * sizeof(struct zentry));
  485.     }
  486.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  487.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  488.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  489.         getstring(code,lzw);
  490.         lzw->next = code + 1;
  491.         lzw->prefix = code;
  492.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  493.             morebits(lzw);
  494.         return;
  495.     }
  496. intable:
  497.     getstring(code,lzw);
  498.     i = (lzw->next - ZFLUSH - 1) / LZWBLK;
  499.     j = (lzw->next - ZFLUSH - 1) % LZWBLK;
  500.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  501.         lzw->tu.tbl[i] = (struct zentry *)
  502.                 mallocw(LZWBLK * sizeof(struct zentry));
  503.         memset((char *)lzw->tu.tbl[i], 0xff,
  504.                 LZWBLK * sizeof(struct zentry));
  505.     }
  506.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  507.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  508.     lzw->next++;
  509.     lzw->prefix = code;
  510.     if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  511.         morebits(lzw);
  512. }
  513.  
  514. /* extract the next codeword from the input stream */
  515. static int32
  516. nextcode(up)
  517. struct usock *up;
  518. {
  519.     int32 code;
  520.     if(up->zin->code == -1) {    /* read the first character */
  521.         if((code = PULLCHAR(&up->ibuf)) == -1)
  522.             return -1;
  523.         up->zin->code = code >> up->zin->nextbit;
  524.     }
  525.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  526.         return -1;
  527.     /* continue assembling the codeword */
  528.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  529.             8 - up->zin->nextbit) & (((int32) 1 <<
  530.             up->zin->codebits) - 1);
  531.     if(16 - up->zin->nextbit < up->zin->codebits) {
  532.         (void) PULLCHAR(&up->ibuf);
  533.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  534.         return nextcode(up);
  535.     }
  536.     code = up->zin->code;
  537.     up->zin->code = -1;
  538.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  539.     if(up->zin->nextbit == 0)
  540.         (void) PULLCHAR(&up->ibuf);
  541.     if(code == ZCC) {
  542.         cleartbl(up->zin);
  543.         return nextcode(up);
  544.     }
  545.     if(code == ZFLUSH) {
  546.         up->zin->prefix = -1;
  547.         return nextcode(up);
  548.     }
  549.     return code;
  550. }
  551.